Server: Netscape-Commerce/1.12
Date: Wednesday, 20-Nov-96 22:45:04 GMT
Last-modified: Friday, 27-Jan-95 20:56:13 GMT
Content-length: 851
Content-type: text/html

<HEADER>
<TITLE>Uses of Randomness in Complexity Theory - Spring 95</title></HEADER>
<BODY>
<H2>Uses of Randomness in Complexity Theory</H2>


<P>
Techniques involving randomness have played a crucial role 
in complexity theory over the past decade. They have been 
used to prove results that seemingly did not call for them, 
such as Toda's theorem, and the fact that many NP-hard 
problems are also NP-hard to  approximate.<P>

The course will survey these developments, at the same time 
putting them in context by also covering ideas from cryptography,
interactive proofs, and program checking that led to them.<P>

The course is scheduled for Tu-Thurs from 10:30 to 12, but that 
could change if many people have conflicts with that.<P>

Prerequisites: Solid Knowledge of NP-completeness and reductions.
	       Some mathematical maturity.<P>



